import java.util.*;

/**
 * 961. 在长度 2N 的数组中找出重复 N 次的元素
 * <p>
 * 给你一个整数数组 nums ，该数组具有以下属性：
 * nums.length == 2 * n.
 * nums 包含 n + 1 个 不同的 元素
 * nums 中恰有一个元素重复 n 次
 * 找出并返回重复了 n 次的那个元素。
 */
public class repeatedNTimes {
    public static void main(String[] args) {
        int[] nums = {5, 1, 5, 2, 5, 3, 5, 4};
        int i = repeatedNTimes_2(nums);
    }

    /**
     * 自己的解决方案
     * <p>
     * 7 ms(38.69%)	41.3 MB(97.77%)
     *
     * @return
     */
    public static int repeatedNTimes_1(int[] nums) {
        if (nums.length < 2) return -1;
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (Objects.equals(nums[j], nums[j + 1])) {
                    return nums[j];
                } else if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
        return -1;
    }

    /**
     * 更好的解法
     * 0 ms(100.00%)	41.9 MB(71.13%)
     *
     * @param nums
     * @return
     */
    public static int repeatedNTimes_2(int[] nums) {
        Set<Integer> found = new HashSet<Integer>();
        for (int num : nums) {
            if (!found.add(num)) {
                return num;
            }
        }
        return -1;
    }
}
